/**
 * 给定一个单词列表words和一个整数 k ，返回前k个出现次数最多的单词。
 *
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
 *https://leetcode.cn/problems/top-k-frequent-words/
 *思路：利用堆和map
 *
 */

import java.util.*;

class TopKFrequent {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map=new HashMap<>();
        for(String word:words){
            if(map.get(word)==null){
                map.put(word,1);
            }else{
                int val=map.get(word);
                map.put(word,val+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(minHeap.size()<k){
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> top=minHeap.peek();
                Integer val=top.getValue();
                if(val.compareTo(entry.getValue())<0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }else if(val.compareTo(entry.getValue())==0){
                    String key=top.getKey();
                    if(key.compareTo(entry.getKey())>0){
                         minHeap.poll();
                    minHeap.offer(entry);
                    }
                }
            }
        }
         List<String> list = new ArrayList<>();
        for(int i=0;i<k;i++){
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}